package developer.算法.堆.数组中第K个最大元素;

import java.util.Arrays;

/**
 * @author zhangyongkang
 * @time 2025/4/7 15:37
 * @description 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * <p>
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3,2,1,5,6,4], k = 2
 * 输出: 5
 * 示例 2:
 * <p>
 * 输入: [3,2,3,1,2,4,5,5,6], k = 4
 * 输出: 4
 */
public class KMax {

    public static void main(String[] args) {
        Solution3 solution = new Solution3();
//        int[] ints = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int[] ints = {3, 2, 1, 5, 6, 4};
        int result = solution.findKthLargest(ints, 2);
        System.out.println("result = " + result);
        System.out.println(Arrays.toString(ints));
    }

    static class Solution3 {
        public int findKthLargest(int[] nums, int k) {
            //先进行堆排序
            buildHeap(nums);
            System.out.println("大根堆:" + Arrays.toString(nums));

            int length = nums.length;
            for (int i = 0; i < k; i++) {
                int nextHead = nums[--length];
                nums[length] = nums[0];
                nums[0] = nextHead;
                maxHeap(nums, 0, length);
            }
            return nums[0];
        }

        private void buildHeap(int[] nums) {
            for (int i = (nums.length / 2) - 1; i >= 0; i--) {//要点： 从下往上构造
                maxHeap(nums, i, nums.length);
            }
        }

        private void maxHeap(int[] nums, int maxId, int maxLength) {
            int left = maxId * 2 + 1;
            int right = maxId * 2 + 2;
            int currentMax = maxId;
            if (left < maxLength && nums[left] > nums[currentMax]) {
                currentMax = left;
            }
            if (right < maxLength && nums[right] > nums[currentMax]) {
                currentMax = right;
            }

            if (currentMax != maxId) {
                //交换 排序
                swap(nums, currentMax, maxId);
                maxHeap(nums, currentMax, maxLength);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }


    static class Solution {
        public int findKthLargest(int[] nums, int k) {
            //构建大根堆
            buildMaxHeap(nums);
            System.out.println("大根堆:" + Arrays.toString(nums));
            //将顶元素删除  （思路，将顶元素和最后一个元素做交换，通过maxSize进行限制）
            int length = nums.length;
            for (int i = nums.length - 1; i > nums.length - k; i--) {
                swap(nums, 0, i);//进行交换  此时的i元素相当于被舍弃了
                maxHeap(nums, 0, --length);
            }
            return nums[0];
        }

        public void buildMaxHeap(int[] nums) {
            int loopSize = nums.length / 2 - 1;// nums.length-1 是最后一个根节点的位置
            for (int i = loopSize; i >= 0; i--) {
                maxHeap(nums, i, nums.length);
            }
        }

        public void maxHeap(int[] nums, int maxIdx, int maxLength) {
            int leftChildrenIdx = maxIdx * 2 + 1;
            int rightChildrenIdx = maxIdx * 2 + 2;
            int largestIdx = maxIdx;

            if (leftChildrenIdx < maxLength && nums[leftChildrenIdx] > nums[largestIdx]) {
                largestIdx = leftChildrenIdx;
            }

            if (rightChildrenIdx < maxLength && nums[rightChildrenIdx] > nums[largestIdx]) {
                largestIdx = rightChildrenIdx;
            }
            if (largestIdx != maxIdx) {//如果当前堆发生改变
                swap(nums, maxIdx, largestIdx);
                maxHeap(nums, largestIdx, maxLength);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcod-2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class SolutionOfficial {
        public int findKthLargest(int[] nums, int k) {
            int heapSize = nums.length;
            buildMaxHeap(nums, heapSize);
            for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
                swap(nums, 0, i);
                --heapSize;
                maxHeapify(nums, 0, heapSize);
            }
            return nums[0];
        }

        public void buildMaxHeap(int[] a, int heapSize) {
            for (int i = heapSize / 2 - 1; i >= 0; --i) {//堆的数量
                maxHeapify(a, i, heapSize);
            }
        }

        public void maxHeapify(int[] a, int i, int heapSize) {
            int l = i * 2 + 1, r = i * 2 + 2, largest = i;
            if (l < heapSize && a[l] > a[largest]) {
                largest = l;
            }
            if (r < heapSize && a[r] > a[largest]) {
                largest = r;
            }
            if (largest != i) {
                swap(a, i, largest);
                maxHeapify(a, largest, heapSize);
            }
        }

        public void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }


}
